package com.zklh.leetcode.top100;

/**
 * 最大子数组和算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/13
 */
public class Solution53 {
    public int maxSubArray(int[] nums) {
        int[] maxSubCache = new int[nums.length];

        maxSubCache[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxSubCache[i] = nums[i] + Math.max(0, maxSubCache[i-1]);
            max = Math.max(max, maxSubCache[i]);
        }
        return max;
    }
}